package com.learn.algorlthm;

/**
 * @classname:
 * @Description:最长不含重复字符的子字符串
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-08-11 16:14
 * 题目描述：
 * 输入一个字符串，（只包含a~z的字符），求其最长不含重复字符的子字符串的长度。例如对于arabcacfr,最长不含重复字符
 * 的子字符串为acfr，长度为4.
 */
public class Learn48 {

    public static int longestSubStringWithoutDuplication(String str) {
        if (str == null || str.length() ==0 )
            return 0;
        int curLen = 0, maxLen = 0;

        int[] dp = new int[256];

        char[] chars = str.toCharArray();

        for (char c : chars) {
            dp[c]++;
            if (dp[c] == 1) {
                curLen++;
            } else {
                curLen = 1;
                dp = new int[256];
                dp[c]++;
            }
            maxLen = Math.max(curLen, maxLen);
        }

        return maxLen;
    }
}
